/*
 * @lc app=leetcode.cn id=1631 lang=cpp
 *
 * [1631] 最小体力消耗路径
 */
#include "include.h"
// @lc code=start
// 并查集模板
// Wow ~

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    // 当前连通分量数目
    int setCount;
    
public:
    UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int findset(int x) {
        return parent[x] == x ? x : parent[x] = findset(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        return true;
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        vector<tuple<int, int, int>> edges;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int id = i * n + j;
                if (i > 0) {
                    edges.emplace_back(id - n, id, abs(heights[i][j] - heights[i - 1][j]));
                }
                if (j > 0) {
                    edges.emplace_back(id - 1, id, abs(heights[i][j] - heights[i][j - 1]));
                }
            }
        }
        sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
            auto&& [x1, y1, v1] = e1;
            auto&& [x2, y2, v2] = e2;
            return v1 < v2;
        });

        UnionFind uf(m * n);
        int ans = 0;
        for (const auto [x, y, v]: edges) {
            uf.unite(x, y);
            if (uf.connected(0, m * n - 1)) {
                ans = v;
                break;
            }
        }
        return ans;
    }
};

// dijkstra

class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        rowNum_ = heights.size();
        colNum_ = heights[0].size();
        vertexNum_ = rowNum_ * colNum_;

        int distance[vertexNum_];
        int path[vertexNum_];
        int finish[vertexNum_];

        memset(distance, 1e6, vertexNum_*sizeof(int));
        memset(path, 0, vertexNum_*sizeof(int));
        memset(finish, 0, vertexNum_*sizeof(int));

        distance_ = distance;
        path_ = path;
        finish_ = finish;
        heightMap_ = &heights;

        dijkstra();

        return distance_[coord2index(rowNum_-1, colNum_-1)];
    }
private:
    void dijkstra(){
        // start -> start init
        distance_[0] = 0;
        finish_[0] = 1;

        // start -> neighbor init
        if (colNum_ > 1)
        distance_[coord2index(0, 1)] = deltaHeight(0, 0, right_);
        if (rowNum_ > 1)
        distance_[coord2index(1, 0)] = deltaHeight(0, 0, down_);

        for (int v=1;v<vertexNum_;++v){
            int minDistance = 1e6;
            int nearestIndex;

            // searching nearest node to v0 (except for these finished nodes)
            // deal with it in this circle
            for (int i=0;i<vertexNum_;++i){
                if (finish_[i] == 0 and distance_[i] < minDistance){
                    nearestIndex = i;
                    minDistance = distance_[i];
                }
            }

            // mark nearest node finished before next loop , which will traverse neighbors of nearest node
            finish_[nearestIndex] = 1;

            // modify dis of neighbors of nearest node
            // for (int i=0;i<vertexNum_;++i){
            
            // 2 dimension map => 2 ~ 4 neighbors for each cell
            auto nearestCoord = index2coord(nearestIndex);
            for (int direct=0;direct<4;++direct){
                // emmmmmm, I need neighbor coord to check neighbor inside , and not finished
                auto neighborCoord = std::make_pair(nearestCoord.first+direction_[direct][0], nearestCoord.second+direction_[direct][1]);
                auto neighborIndex = coord2index(neighborCoord.first, neighborCoord.second);
                if (!insideMap(neighborCoord.first, neighborCoord.second)){continue;}
                if (finish_[neighborIndex] == 1){continue;}

                // modify, if dis descends in condition of passing by nearest node
                // int newDis = minDistance + dis(nearest, neighbor);
                int newDis = std::max(minDistance, deltaHeight(nearestCoord.first, nearestCoord.second, direct));
                if (newDis < distance_[neighborIndex]){
                    distance_[neighborIndex] = newDis;
                    path_[neighborIndex] = nearestIndex;
                }
            }
        }
    }
private:
    int rowNum_, colNum_, vertexNum_;
    int* distance_, *path_, *finish_;
    int direction_[4][2] = {
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1}
    };
    enum direct_{
        up_ = 0,
        down_ = 1,
        left_ = 2,
        right_ = 3
    };
    vector<vector<int>>* heightMap_;
private:
    inline int deltaHeight(int row, int col, int direct){
        return std::abs((*heightMap_)[row][col] - (*heightMap_)[row+direction_[direct][0]][col+direction_[direct][1]]);
    }
    inline bool insideMap(int row, int col){
        return row >= 0 and row < rowNum_ and col >= 0 and col < colNum_;
    }
    inline int coord2index(int row, int col){
        return row * colNum_ + col;
    }
    inline std::pair<int, int> index2coord(int index){
        return std::make_pair<int, int>(index / colNum_, index % colNum_);
    }
};
// @lc code=end

int main(){
    vector<vector<int>> heights = {
        // {1,2,2},
        // {3,8,2},
        // {5,3,5}
        {3}
    };
    // [[3]]
    Solution test;
    test.minimumEffortPath(heights);
}
